package edu.cast.teseg.modelo;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author edgarin
 */
public class Dijkstra {
    
    
    private int[][] w = new int[13][13];
    private int[] pesos = new int[w.length];
    private int[] cola = new int[w.length];
    private int[] caminos = new int[w.length];
    
    
    public Dijkstra() {
        w[0][0]=0;
        w[0][1]=1;
        w[0][2]=999;
        w[0][3]=1;
        w[0][4]=999;
        w[0][5]=999;
        w[0][6]=999;
        w[0][7]=999;
        w[0][8]=999;
        w[0][9]=999;
        w[0][10]=999;
        w[0][11]=999;
        w[0][12]=999;
        
        w[1][0]=1;
        w[1][1]=0;
        w[1][2]=1;
        w[1][3]=999;
        w[1][4]=999;
        w[1][5]=999;
        w[1][6]=999;
        w[1][7]=999;
        w[1][8]=999;
        w[1][9]=999;
        w[1][10]=999;
        w[1][11]=999;
        w[1][12]=999;
        
        w[2][0]=999;
        w[2][1]=1;
        w[2][2]=0;
        w[2][3]=1;
        w[2][4]=999;
        w[2][5]=999;
        w[2][6]=1;
        w[2][7]=999;
        w[2][8]=999;
        w[2][9]=999;
        w[2][10]=999;
        w[2][11]=999;
        w[2][12]=999;
        
        w[3][0]=1;
        w[3][1]=999;
        w[3][2]=1;
        w[3][3]=0;
        w[3][4]=1;
        w[3][5]=1;
        w[3][6]=1;
        w[3][7]=999;
        w[3][8]=999;
        w[3][9]=999;
        w[3][10]=999;
        w[3][11]=999;
        w[3][12]=999;
        
        w[4][0]=999;
        w[4][1]=999;
        w[4][2]=999;
        w[4][3]=1;
        w[4][4]=0;
        w[4][5]=1;
        w[4][6]=999;
        w[4][7]=999;
        w[4][8]=999;
        w[4][9]=999;
        w[4][10]=1;
        w[4][11]=999;
        w[4][12]=999;
        
        w[5][0]=999;
        w[5][1]=999;
        w[5][2]=999;
        w[5][3]=1;
        w[5][4]=1;
        w[5][5]=0;
        w[5][6]=1;
        w[5][7]=1;
        w[5][8]=1;
        w[5][9]=999;
        w[5][10]=1;
        w[5][11]=999;
        w[5][12]=999;
        
        w[6][0]=999;
        w[6][1]=999;
        w[6][2]=1;
        w[6][3]=1;
        w[6][4]=999;
        w[6][5]=1;
        w[6][6]=0;
        w[6][7]=1;
        w[6][8]=999;
        w[6][9]=999;
        w[6][10]=999;
        w[6][11]=999;
        w[6][12]=999;
        
        w[7][0]=999;
        w[7][1]=999;
        w[7][2]=999;
        w[7][3]=999;
        w[7][4]=999;
        w[7][5]=1;
        w[7][6]=1;
        w[7][7]=0;
        w[7][8]=1;
        w[7][9]=999;
        w[7][10]=999;
        w[7][11]=999;
        w[7][12]=999;
        
        w[8][0]=999;
        w[8][1]=999;
        w[8][2]=999;
        w[8][3]=999;
        w[8][4]=999;
        w[8][5]=1;
        w[8][6]=999;
        w[8][7]=1;
        w[8][8]=0;
        w[8][9]=1;
        w[8][10]=999;
        w[8][11]=1;
        w[8][12]=1;
        
        w[9][0]=999;
        w[9][1]=999;
        w[9][2]=999;
        w[9][3]=999;
        w[9][4]=999;
        w[9][5]=999;
        w[9][6]=999;
        w[9][7]=999;
        w[9][8]=1;
        w[9][9]=0;
        w[9][10]=999;
        w[9][11]=999;
        w[9][12]=999;
        
        w[10][0]=999;
        w[10][1]=999;
        w[10][2]=999;
        w[10][3]=999;
        w[10][4]=1;
        w[10][5]=1;
        w[10][6]=999;
        w[10][7]=999;
        w[10][8]=999;
        w[10][9]=999;
        w[10][10]=0;
        w[10][11]=1;
        w[10][12]=999;
        
        w[11][0]=999;
        w[11][1]=999;
        w[11][2]=999;
        w[11][3]=999;
        w[11][4]=999;
        w[11][5]=999;
        w[11][6]=999;
        w[11][7]=999;
        w[11][8]=1;
        w[11][9]=999;
        w[11][10]=1;
        w[11][11]=0;
        w[11][12]=1;
        
        w[12][0]=0;
        w[12][1]=1;
        w[12][2]=999;
        w[12][3]=1;
        w[12][4]=999;
        w[12][5]=999;
        w[12][6]=999;
        w[12][7]=999;
        w[12][8]=1;
        w[12][9]=999;
        w[12][10]=999;
        w[12][11]=1;
        w[12][12]=0;
        
        
    }
    
    
     public void iniciarUnSoloOrigen(int[] pesosVG,int origen){
        for (int i = 0; i < w.length; i++) {
            pesosVG[i]=999;            
            caminos[i]=999;            
            
        }
        pesosVG[origen]= 0;        
    }
      
    public void relajacion(int u, int[] verticeG, int w[][], boolean[] visitadoVG){
        //******************** Extructira Optima **************************
        for (int i = 0; i < verticeG.length; i++) {
            if(verticeG[i] > (verticeG[u] + w[u][i])&&!visitadoVG[i]){
                verticeG[i] = verticeG[u] + w[u][i];
                caminos[i] = u;
            }
        }
        //*****************************************************************
        
    }
       
    public void ejecutaDijkstra(){
        
        final boolean [] visitadoVG = new boolean [w.length];

        iniciarUnSoloOrigen(pesos,0);
        
        cola = pesos;
        
     
        for (int i = 0; i < w.length; i++) {
            
            final int u = ExtraerMin.getExtraerMin(cola, visitadoVG);
            
            visitadoVG[u]=true;
            
            relajacion(u, pesos, w, visitadoVG);              
            
        }
      
        System.out.print("termine");
      }

    public int[][] getMatriz(){    
        return w;
    }
     
}
